package com.example.designpatterns.strategy.sorting;

import com.example.designpatterns.strategy.Strategy;
import java.util.Arrays;

/**
 * 计数排序策略 - 使用计数排序算法实现排序
 * 时间复杂度：O(n+k)，其中k是数据范围
 * 空间复杂度：O(k)
 * 稳定性：稳定
 * 适用于数据范围不大的整数排序
 */
public class CountingSortStrategy implements Strategy<int[], int[]> {
    
    @Override
    public int[] execute(int[] input) {
        if (input == null || input.length <= 1) {
            return input;
        }
        
        // 创建数组副本，不修改原始数据
        int[] array = Arrays.copyOf(input, input.length);
        int n = array.length;
        
        // 找到数组中的最大值和最小值
        int max = array[0], min = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        
        // 计算计数数组大小，并处理可能的负数
        int range = max - min + 1;
        
        // 创建计数数组并统计每个元素出现的次数
        int[] count = new int[range];
        for (int i = 0; i < n; i++) {
            count[array[i] - min]++;
        }
        
        // 计算累积计数，确定元素的实际位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        
        // 创建结果数组
        int[] result = new int[n];
        
        // 从后向前遍历原数组，确保排序的稳定性
        for (int i = n - 1; i >= 0; i--) {
            result[count[array[i] - min] - 1] = array[i];
            count[array[i] - min]--;
        }
        
        // 将结果复制回原数组
        System.arraycopy(result, 0, array, 0, n);
        
        return array;
    }
} 